package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author lchenglong
 * @date 2022/6/24
 */
public class 在二叉树中增加一行 {

    public static void main(String[] args) {
        TreeNode root = TreeNode.init(new ArrayList<>(Arrays.asList(4,2,6,3,1,5)));
        Solution solution = new Solution();
        TreeNode treeNode = solution.addOneRow(root, 1, 2);
        TreeNode.print(treeNode);
    }
    static class Solution {
        int depth;
        int val;
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            this.depth = depth;
            this.val = val;
            // root节点对应的深度
            if (this.depth == 1){
                TreeNode pre = new TreeNode(val);
                pre.left = root;
                return pre;
            } else {
                travel(root, 1);
                return root;
            }
        }

        public void travel(TreeNode root,int curDepth){
            if (root == null) return ;

            if (curDepth == depth-1){
                // 定位到cur节点
                TreeNode left = new TreeNode(this.val);
                left.left = root.left;
                root.left = left;
                TreeNode right = new TreeNode(this.val);
                right.right = root.right;
                root.right= right;
            }
            travel(root.left,curDepth+1);
            travel(root.right,curDepth+1);
        }
    }
}
